Field of the Invention
The present invention generally relates to graphics processing and more specifically to baking path rendering objects into compact and efficient memory representations.
Description of the Related Art
Path rendering is a style of resolution-independent two-dimensional (2D) rendering that is the basis for a number of important rendering standards such as PostScript, Java 2D, Apple's Quartz 2D, OpenVG, PDF, TrueType fonts, OpenType fonts, PostScript fonts, Scalable Vector Graphics (SVG) web format, Microsoft's Silverlight and Adobe Flash for interactive web experiences, Open XML Paper Specification (OpenXPS), drawings in Office file formats including PowerPoint, Adobe Illustrator illustrations, and more.
In the context of path rendering, the term resolution-independent means that an image is described by paths without regard to the pixel resolution of a resulting rendered image or associated frame buffer. This is in contrast to the resolution-dependent nature of bitmapped graphics, which is tied to a particular 2D image resolution. Unlike images specified by using bitmapped graphics, images specified with path rendering can be rendered at arbitrary resolutions or arbitrarily transformed without blurring or pixilation typically associated with such operations when performed on a bitmapped image.
Sometimes the term vector graphics is used to mean path rendering, but path rendering refers to a specific approach for rendering an image. While vector graphics could be any computer graphics approach that represents resolution-independent objects (typically 2D), path rendering is a much more specific rendering model with salient features that include path filling, path stroking, dashing, path masking, compositing, and path segments specified as Bèzier curves.
FIG. 1A is a prior art image specified by a sequence of paths for path rendering. Path rendering is analogous to how an artist draws with pens and brushes to sequentially compose an image. The path sequence defines a specific order for rendering the paths. Each path is specified as a sequence of path commands and a corresponding set of coordinates. Each path command may specify one or more sub-paths. Each sub-path (also called a trajectory) is a connected sequence of line segments and/or curved segments. Each sub-path may be closed, meaning the sub-path's start and terminal points are the same location so the stroke forms a loop; alternatively, a sub-path can be open, meaning the sub-path's start and terminal points are distinct. As shown, the paths are stroked but not filled.
FIG. 1B is the prior art image of FIG. 1A with both stroking and filling. As shown, a first path is stroked with black and filled with white, while a second path behind the first path is stroked with black and filled with gray. When a path is both filled and stroked, typically the stroking operation is done immediately subsequent to the filling operation so the stroking outlines the filled region. Artists tend to use stroking and filling together in this way to help highlight or offset the filled region so typically the stroking is done with a different color than the filling.
FIG. 1C illustrates the prior art image of FIG. 1A rendered with filling but without stroking. As shown, the first path is filled with white, while the second path behind the first path is filled with gray. Without stroking, the first path is only visible in this setting in that it covers portions of the second path with white.
Filling is similar to the way a child would “color in between the lines” of a coloring book. If a sub-path within a path is not closed when such a sub-path is filled, the standard practice is to force the sub-path closed by connecting its end and start points with an implicit line segment, thereby closing the sub-path, and then filling that resulting closed path. While the meaning of “inside a path” generally matches the intuitive meaning of this phrase, path rendering formalizes this notion with what is called a fill-rule. The intuitive sense of “inside” is sufficient as long as a closed sub-path does not self-intersect itself. However if a sub-path intersects itself or another sub-path or some sub-paths are fully contained within other sub-paths, what it means to be inside or outside the path needs to be better specified.
Stroking is distinct from filling and is analogous to tracing or outlining each sub-path comprising a path as if with a pen or marker defined by a certain width. Stroking operates on the perimeter or boundary defined by the path whereas filling operates on the path's interior. Unlike filling, there is no requirement for the sub-paths within a path to be closed for stroking. For example, the curve of a letter “S” could be stroked without having to be closed though the curve of the letter “O” could also be stroked.
A stroke for a path may be embellished using dashing that interrupts the stroke with gaps that are specified by a repeated pattern of on-off lengths, called a dash pattern. The dash pattern for a particular path may begin at an initial offset into the dash pattern other than zero; this offset is known as the dash offset. The dash offset essentially shifts the dash pattern up or down (if negative) the path. Each end of a dash may be specified by a certain form of cap, such as a flat or round cap. Dashing is common in technical illustration. Dashing is helpful in distinguishing different types of lines or connections. Artists also make use of dashing to accomplish various artistic effects.
FIG. 1D illustrates the prior art image of FIG. 1B, including dashed stroked paths for the second path.
Dashing curved paths is challenging because it requires the computation of incremental arc lengths along a dashed path. Computing the length of a cubic Bèzier segment or partial elliptical arc lacks a tractable closed form solution and is therefore extremely difficult. Closed form analytic equations for the arc lengths of cubic Bèzier segments and arcs limited to elementary functions do not exist.
Graphics processing units (GPUs) conventionally include features to accelerate three-dimensional (3D) graphics and certain 2D bitmapped graphics functions. GPUs provide extremely high-throughput processing for certain classes of computations compared to a traditional central processing unit (CPU). In today's systems, however, nearly all path rendering is performed by the CPU via scan-line rendering with no acceleration by a GPU. GPUs do not conventionally render curved primitives as a native rendering operation, so path rendering primitives such as Bèzier segments and partial elliptical arcs must be approximated by lots of tiny triangles for a GPU to render such curve primitives. Constructing the required tessellations of a path that is approximated by many short connected line segments. This process can create a substantial CPU burden. The triangles or other polygons resulting from tessellation are then rendered by the GPU. Because GPUs are so fast at rasterizing triangles, tessellating paths into polygons that can then be rendered by GPUs is an obvious approach to GPU-accelerating path rendering.
Tessellation is a fragile, often quite sequential, process that requires global inspection of the entire path. Tessellation depends on dynamic data structures to sort, search, and otherwise manipulate the incremental steps involved in generating a tessellation for a path. Path rendering makes this process considerably more difficult by permitting curved path segments as well as allowing path segments to self-intersect, form high genus topologies, and be unbounded in size. Performance burdens associated with complex CPU-based tessellation for GPU-based rendering can result in poor overall performance.
A general problem with using a GPU to render paths is unacceptably poor antialiasing quality when compared to standard CPU-based methods. The problem is that GPUs employ point sampling for rasterization of triangular primitives with only 1 to 8 samples (often 4) per pixel. CPU-based scan-line methods typically employ 16 or more samples per pixel and can accumulate coverage over horizontal spans for higher-quality antialiasing.
Animating or editing paths is costly because it requires re-tessellating the entire path since the tessellation is resolution and view dependent, and in general it is very difficult to prove a local edit to a path will not cause a global change in the tessellation of the path. Furthermore, when curved path segments are present and the scaling of the path with respect to pixel space changes appreciably (zooming in say), the curved path segments may need to be re-subdivided and re-tessellation is likely to be necessary.
Additionally, compositing in path rendering systems typically requires that pixels rasterized by a filled or stroked path are updated once-and-only-once per rasterization of the path. This requirement means non-overlapping tessellations are required. So for example, a cross cannot be tessellated as two overlapping rectangles but rather must be rendered by the outline of the cross, introducing additional vertices and primitives. In particular, this means the sub-paths of a path cannot be processed separately without first determining that no two sub-paths overlap. These requirements, combined with the generally fragile and sequential nature of tessellation algorithms make path tessellation particularly expensive. Because of the expense required in generating tessellations, it is very tempting and pragmatic to cache tessellations. Unfortunately such tessellations are much less compact than the original path representations, particularly when curved path segments are involved. Consequently, a greater amount of data must be stored to cache paths after tessellation compared with storing the paths prior to tessellation. Cached tessellations are also ineffective when paths are animated or rendered just once.
Conventional stroking can be performed by approximating paths into sub-pixel linear segments and then tracing the segments with a circle having a diameter equal to a stroke width. Offset curves are generated at the boundary of the stroked path. These offset curves are typically of much higher degree of complexity compared with the linear segments that are traced to generate the stroked path. Determining whether or not each pixel is inside or outside of a stroked path to generate a given stroke is mathematically complex. Identification of the pixels to be stroked is equivalent to identifying pixels that are within half of the stroke width of any point along the path to be stroked. More specifically, the pixels to be stroked are within half of the stroke width measured along a line that is perpendicular to the tangent of the path segment being stroked.
The tangent of a sub-path is not necessarily well-defined at junctions between path segments. So additional rules are needed to determine what happens at and in the vicinity of such junctions as well as what happens at the terminal (start and end) points of sub-paths. Therefore stroking specifies further stroking rules to handle these situations.
In standard path rendering systems, paths are specified as a sequence of cubic and quadratic (non-rational) Bèzier curve segments, partial elliptical arcs, and line segments. While more mathematically complex path segments representations could be used to specify paths, in practice, existing standards limit themselves to the aforementioned path segment types.
Path filling and stroking use the same underlying path specification. For filling, this means the resulting piece-wise boundaries to be filled may be up to third-order (in the case of cubic Bèzier segments) or rational second-order (in the case of partial elliptical arcs). Filling these curved boundaries of Bèzier curves and arcs is clearly more complex than filling the standard polygonal primitives in conventional polygonal 2D or 3D rendering where the boundaries (edges) of the polygonal primitives (usually triangles) are all first-order, being linear segments, and often required to be convex. Filling and stroking operations on the curves and arcs are also more complex than conventional line and convex polygon rasterization because paths are unbounded in their complexity whereas line segments and triangles are defined by just 2 or 3 points respectively. A path may contain just a single path segment or it could contain thousands or more.
The boundaries of stroked paths are actually substantially higher order than the third-order segments. The offset curve of non-rational (second-order) quadratic and (third-order) Bèzier curves are eighth- and tenth-order curves respectively. This high order makes exact determination and evaluation of the resulting offset curves for such Bèzier segments intractable for use in direct rendering. In other words, it is quite unreasonable to try to determine exactly the boundary representation of such offset curves and then simply fill them. For this reason, various techniques have been developed to approximate offset curves with sequences of Bèzier, arc, or line segments. These approximate stroke boundaries may then be filled using significantly less complex techniques.
GPU acceleration can provide a significant performance improvement for certain graphics applications, such as 3D rendering and 2D image processing. However, for the reasons described above, path rendering in the prior art does not benefit as significantly from GPU involvement. Accordingly, what is needed in the art is an improved system and method for path rendering with a GPU.